class Solution(object):
    def newInteger(self, n):
        """
        :type n: int
        :rtype: int
        """
        DP = [0]
        i = 0
        self.n = n
        while True:
            k = 9 * DP[i] + 10 ** i
            if 10 ** (i + 1) - k <= n:
                DP.append(k)
                i += 1
            else:
                break
        DP.reverse()

        def search(k):
            base = 10 ** (i - k)
            m = 1
            while m < 9:
                if m * (base - DP[k]) > self.n:
                    break
                else:
                    m += 1
            self.n -= (m - 1) * (base - DP[k])
            return m - 1

        total = 0
        for k in range(i + 1):
            total += search(k) * 10 ** (i - k)
        return total


data = Solution()
n = 9
print(data.newInteger(n))
